/*
 * @Author: your name
 * @Date: 2024-03-22 10:08:26
 * @LastEditTime: 2024-03-22 10:41:16
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\977.有序数组的平方.cpp
 */
/*
 * @lc app=leetcode.cn id=977 lang=cpp
 *
 * [977] 有序数组的平方
 */

// @lc code=start
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        
        vector<int> ans(nums.size());
        int index = right;
        while(left <= right){
            int left_val = nums[left] * nums[left];
            int right_val = nums[right] * nums[right];
            if(left_val>right_val){
                ans[index--] = left_val;
                left++;
            }else{
                ans[index--] = right_val;
                right--;
            }
        }
        return ans;
    }   
};
// @lc code=end
//题目没有对空间有要求，申请一个一样大小的空间，双指针从
//原数组两头寻找数组的最大值，从后面插入。
